\documentclass[t,10pt,aspectratio=169]{beamer} % 16:9 宽屏比例，适合现代投影
\usepackage{ctex} % 中文支持
\usepackage{amsmath, amssymb} % 数学公式与符号
\usepackage{graphicx}
\usepackage{pythonhighlight}
\usepackage{url}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% 使表格美观
\usepackage{array}
\newcolumntype{M}[1]{>{\centering\arraybackslash}m{#1}}
%\newcolumntype{N}{@{}m{0pt}@{}}
\setlength\extrarowheight{3pt}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% 主题设置（推荐简洁风格）
\usetheme{Madrid}
\usecolortheme{default} % 可选：seahorse, beaver, dolphin 等

\title{奇异值分解与数据压缩 }
\author{五六七}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}

\begin{frame}
  \titlepage
\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{内容提要 }

\begin{enumerate}
\item  将一个矩阵数据用更少的空间保存。
\item  矩阵的奇异值分解。
\end{enumerate}

\end{frame}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{目录}

\begin{enumerate}
\item  问题描述
\item  建立模型
\item  编程计算
\item  回答问题
\item  习题

\end{enumerate}

\end{frame}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{1.1. 问题描述 }

\begin{itemize}\itemsep0.5em 

\item  一张图片一般是长方形的，每个像素由一个整数或一个浮点型数据表示。
这样的图片可以由一个矩阵来保存，称为 bmp 格式。
使用矩阵的奇异值分解的方法，用更少的空间来保存这个矩阵的数据。

\begin{center}
\includegraphics [height=5cm, width=8cm]{rice3.png}
\end{center}

\end{itemize}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{2.1. 建立模型 - 奇异值分解定理 }

\begin{itemize}\itemsep0.5em 

\item   设有 $m\times n$ 阶的矩阵 $A$, 奇异值分解是说存在 $m$ 阶正交矩阵 $U$,  和 $n$ 阶正交矩阵 $V$, 以及 $m\times n$ 阶矩阵 $\Sigma$, 其对角线之外的元素都是零，其对角线元素都是非负的，使得
\begin{eqnarray}
A = U\Sigma V^T, 
\end{eqnarray}
其中 $V^T$ 是 $V$ 的转置。

\item   矩阵 $\Sigma$ 的对角线元素从大到小排列，设为 
\begin{eqnarray}
\sigma_1\ge \sigma_2\ge\cdots\ge\sigma_r\ge 0, 
\end{eqnarray}
称为奇异值。其中 $r=R(A)$ 为矩阵 $A$ 的秩。


\end{itemize}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{2.2. 奇异值分解定理 }

\begin{center}
\includegraphics [height=0.55\textheight, width=0.9\textwidth]{svd-by-graph.png}
\end{center}


\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{2.3. 数据压缩的基本思路 }

\begin{itemize}\itemsep0.5em 

\item  压缩的基本思路是选取这些奇异值的前面较大的几个，设为
$$\sigma_1, \sigma_2, \cdots, \sigma_p, $$ 
其中 $p<r$, 而将后面较小的奇异值 
$$\sigma_{p+1}, \sigma_{p+2}, \cdots, \sigma_r $$ 
都忽略为零，从而得到矩阵 $\Sigma_1$. 这时相应的数据矩阵就转化为
\begin{eqnarray}
A_1 = U\Sigma_1 V^T.  
\end{eqnarray}
注意到矩阵 $A_1$ 的秩为 $p$. 


\end{itemize}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{2.4. 分块矩阵计算 }

\begin{itemize}\itemsep0.5em 

\item  记矩阵 $\Sigma_{11}$ 为对角线元素为 $\sigma_1, \sigma_2, \cdots, \sigma_p$ 的对角矩阵，则 $\Sigma_1$ 可以写成分块矩阵的形式 
\begin{eqnarray}
\Sigma_1 = \begin{pmatrix} \Sigma_{11} & O \\ O & O \end{pmatrix}.  
\end{eqnarray}

\item  将矩阵 $U$ 按照左右分块，其中左边矩阵为 $p$ 个列向量，右边矩阵为 $m-p$ 的列向量，可记
\begin{eqnarray}
U = \begin{pmatrix} U_1 & U_2 \end{pmatrix}.  
\end{eqnarray}

\item  将矩阵 $V^T$ 按照上下分块，其中上边矩阵为 $p$ 个行向量，下边矩阵为 $n-p$ 的行向量，可记
\begin{eqnarray}
V^T = \begin{pmatrix} V_1^T \\ V_2^T \end{pmatrix}.  
\end{eqnarray}


\end{itemize}

\end{frame}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{2.5. 实现用较少数据保存 }

\begin{itemize}\itemsep0.5em 

\item  于是按照分块矩阵的乘法，可得 
\begin{eqnarray}
A_1 = U\Sigma_1 V^T = 
\begin{pmatrix} U_1 & U_2 \end{pmatrix}
\begin{pmatrix} \Sigma_{11} & O \\ O & O \end{pmatrix}
\begin{pmatrix} V_1^T \\ V_2^T \end{pmatrix} 
= U_1\Sigma_{11} V_1^T. 
\label{eqn-7}
\end{eqnarray}


\item  这意味着为了保存矩阵 $A_1$,  只需要保存矩阵 $U_1$, $\Sigma_{11}$ 与 $V_1^T$. 

\item  注意到矩阵 $U_1$ 是 $m\times m$ 阶矩阵 $U$ 的左边的 $p$ 个列向量，
矩阵 $V_1^T$ 是 $n\times n$ 阶矩阵 $V^T$ 的上面的 $p$ 个行向量，
因此，所需要保存的数据个数为
\begin{eqnarray}
pm+p+pn. 
\end{eqnarray}

\item  当 $p$ 远远小于 $m$ 与 $n$ 的时候，这个数字会远远少于原始矩阵的 $mn$ 个数据。


\end{itemize}

\end{frame}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{2.6. 奇异值分解的例子（书上例子3.5） }

\begin{itemize}\itemsep0.5em 

\item  {\color{red}问题：试求矩阵 $A=\begin{bmatrix}  1&0&1 \\ 0&1&1 \\ 0&0&0  \end{bmatrix}$ 的奇异值分解。}

%\item  %解答：
%\begin{enumerate}

\item[1.]  计算 $A^tA$ 的特征值，从大到小排列为 
$$\lambda_1=3,\lambda_2=1,\lambda_3=0.$$

\item[2.]  计算相应的特征向量为
$$
\xi_1=\begin{bmatrix} 1 \\ 1 \\ 2  \end{bmatrix},\,\,\,
\xi_2=\begin{bmatrix} 1 \\ -1 \\ 0  \end{bmatrix},\,\,\,
\xi_3=\begin{bmatrix} 1 \\ 1 \\ -1  \end{bmatrix}. 
$$

%\end{enumerate}
\end{itemize}

\end{frame}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{2.7.  }

\begin{itemize}\itemsep0.5em 

\item[3.]  舍弃 $A^tA$ 的等于零的特征值，并取非零特征值的平方根，
记 $$\Sigma=\begin{bmatrix}  \sqrt{3}&0 \\ 0&1 \\   \end{bmatrix}, 
B=\begin{bmatrix}  \Sigma&0 \\ 0&0  \end{bmatrix}
=\begin{bmatrix}  \sqrt{3}&0&0 \\ 0&1&0 \\ 0&0&0  \end{bmatrix}. 
$$

\item[4.]  将特征向量规范化和正交化，可得正交矩阵与对角化的等式，
$$V=\begin{bmatrix} 
\frac{1}{\sqrt{6}} &\frac{1}{\sqrt{2}} &\frac{1}{\sqrt{3}}  \\ 
\frac{1}{\sqrt{6}} &-\frac{1}{\sqrt{2}} &\frac{1}{\sqrt{3}}  \\ 
\frac{2}{\sqrt{6}} &0 &-\frac{1}{\sqrt{3}}
\end{bmatrix}, \,\,\,
V^tA^tAV=BB.
$$

（注：实对称阵的不同特征值的特征向量是相互正交的。）

\end{itemize}

\end{frame}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{2.8.  }

\begin{itemize}\itemsep0.5em 

\item[5.]  
取 $U=\begin{pmatrix} U_1 & U_2 \end{pmatrix}$ 和 $V=\begin{pmatrix} V_1 & V_2 \end{pmatrix}$, 其中第二列是列向量。
则从 $A=UBV^t$ 可得 $AV = UB$, 从而可得 $AV_1=U_1\Sigma$. 于是 
$$U_1=AV_1\Sigma^{-1}=
\begin{bmatrix} 
\frac{1}{\sqrt{2}} &\frac{1}{\sqrt{2}} \\ 
\frac{1}{\sqrt{2}} &-\frac{1}{\sqrt{2}} \\ 
0 & 0.
\end{bmatrix}. $$

\item[6.]  取   $$U=\begin{pmatrix} U_1 & U_2 \end{pmatrix}
=\begin{bmatrix} 
\frac{1}{\sqrt{2}} &\frac{1}{\sqrt{2}} & 0 \\ 
\frac{1}{\sqrt{2}} &-\frac{1}{\sqrt{2}} & 0 \\ 
0 & 0 & 1 \\
\end{bmatrix}. $$


\end{itemize}

\end{frame}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{2.9.  }

\begin{itemize}\itemsep0.5em 

\item[7.]  最后得到奇异值分解为
 \begin{eqnarray*}
  A &=& U\Sigma V^t, \\
 \begin{bmatrix}  1&0&1 \\ 0&1&1 \\ 0&0&0  \end{bmatrix}
&=& \begin{bmatrix} 
 \frac{1}{\sqrt{2}} &\frac{1}{\sqrt{2}} & 0 \\ 
\frac{1}{\sqrt{2}} &-\frac{1}{\sqrt{2}} & 0 \\ 
0 & 0 & 1 \\
\end{bmatrix} 
\begin{bmatrix}  \sqrt{3}&0&0 \\ 0&1&0 \\ 0&0&0 \\ \end{bmatrix}
\begin{bmatrix} 
\frac{1}{\sqrt{6}} &\frac{1}{\sqrt{2}} &\frac{1}{\sqrt{3}}  \\ 
\frac{1}{\sqrt{6}} &-\frac{1}{\sqrt{2}} &\frac{1}{\sqrt{3}}  \\ 
\frac{2}{\sqrt{6}} &0 &-\frac{1}{\sqrt{3}}
\end{bmatrix}^t. 
\end{eqnarray*}

\item[8.] 小结：
\begin{enumerate}
\item[(1)]  $U,V$ 是正交矩阵，矩阵 $\Sigma$ 的对角线之外的元素都为零。
\item[(2)]  矩阵 $\Sigma$ 的对角线元素是对称矩阵 $A^tA$ 的特征值的平方根。
\item[(2)]  矩阵 $\Sigma$ 的对角线元素从大到小排列。
\end{enumerate}
\end{itemize}

\end{frame}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[fragile]{2.10. 使用svd函数计算 }

\begin{python}
#程序文件ex3_5.py
import numpy as np
from numpy.linalg import svd

a = np.array([[1, 0, 1], [0, 1, 1], [0, 0, 0]])
u,s,vt = svd(a)  
a1=u@np.diag(s)@vt
print(u,'\n')
print(s,'\n')
print(vt,'\n')
print(a1)
\end{python}


\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[fragile]{2.11. 使用svd函数计算（输出结果） }

\begin{python}
[[ 0.70710678 -0.70710678  0.        ]
 [ 0.70710678  0.70710678  0.        ]
 [ 0.          0.          1.        ]] 

[ 1.73205081  1.         -0.        ] 

[[ 4.08248290e-01  4.08248290e-01  8.16496581e-01]
 [-7.07106781e-01  7.07106781e-01  2.22044605e-16]
 [ 5.77350269e-01  5.77350269e-01 -5.77350269e-01]] 

[[1.00000000e+00 0.00000000e+00 1.00000000e+00]
 [1.66533454e-16 1.00000000e+00 1.00000000e+00]
 [0.00000000e+00 0.00000000e+00 0.00000000e+00]]
\end{python}


\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[fragile]{3.1. 编程计算 }

\begin{itemize}\itemsep0.5em 

\item  读取所给的图像，得到 $400\time 600\times 3$ 的矩阵数据。这个图像是彩色的，有 RGBA 四层，每层都是一个 $400\times 600$ 的矩阵数据。

\item  首先读入图像，保存为矩阵 $A$. 然后记矩阵 $B$ 是 $A$ 的第一层。
\begin{python}
import numpy as np
import matplotlib.pyplot as plt

A=plt.imread('rice3.png')
B=A[:,:,0]
\end{python}

\item  调用 svd 函数进行奇异值分解，返回两个正交矩阵，和一个对角矩阵。
\begin{python}
U,S,Vh = np.linalg.svd(B)
\end{python}


\end{itemize}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[fragile]{3.2. 编程计算 }

\begin{itemize}\itemsep0.5em 

\item  设 $p=10$, 取正交矩阵 $U$ 的前 $p$ 个列向量，取对角矩阵 $\Sigma$ 的左上角的 $p\times p$ 矩阵，取正交矩阵 $V^T$ 的上面 $p$ 个行向量。
\begin{python}
m=400; n=600; p=10
U1=U[:,0:p]
S11=np.diag(S[0:p])
Vh1=Vh[0:p,:]
\end{python}

\item  为恢复图像，按照分块矩阵的乘法，只需要计算等式(\ref{eqn-7}) 的最右边。
\begin{python}
B1=U1@S11@Vh1
\end{python}


\end{itemize}

\end{frame}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[fragile]{3.3. 编程计算 }

\begin{itemize}\itemsep0.5em 

\item  分左右显示原图和仅使用10个奇异值得到的恢复图像，并分别计算存储所需空间。

\begin{python}
fig = plt.figure()
ax=fig.add_subplot(121)
ax.imshow(B,cmap='summer')
bx=fig.add_subplot(122)
bx.imshow(B1,cmap='summer')

print('Number of floats in the left figure: ',np.size(B))
print('Number of floats in the right figure: ',np.size(U1)+np.size(S11)+np.size(Vh1))
\end{python}


\end{itemize}

\end{frame}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{4.1. 回答问题 }

\begin{itemize}\itemsep0.5em 

\item  
我们取了原图RGB数据的第一个二维矩阵数据，得到一个 $400\times 600$ 的矩阵。
使用奇异值分解，然后取前10个奇异值。然后重新计算矩阵，画出两个矩阵的图像。
左图使用240000个浮点型数值，右图使用10100个浮点型数值。压缩比例大约是1:24. 

\begin{center}
\includegraphics [height=0.5\textheight, width=0.9\textwidth]{rice4.png}
\end{center}


\end{itemize}

\end{frame}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{5.1. 习题 }

\begin{enumerate}\itemsep0.5em 

\item  手工计算下述矩阵的奇异值分解，
\begin{eqnarray}
A = \begin{pmatrix} -3 & 0 \\ 0 & 2 \end{pmatrix}. 
\end{eqnarray}

\item  程序计算下述矩阵的奇异值分解，
\begin{eqnarray}
B = \begin{pmatrix} 3&2&-2&-3 \\ 2&4&-1&-5 \end{pmatrix}. 
\end{eqnarray}

\end{enumerate}

\end{frame}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{参考文献  }

\begin{thebibliography}{1}

\bibitem{sishoukui-2} 司守奎,孙玺菁. {Python数学建模算法与应用}, 国防工业出版社. 2022年1月第1版. 
%\bibitem{rosen-dm6}Kenneth H. Rosen 著, 袁崇义, 屈婉玲, 张桂芸等译. \emph{离散数学及其应用}, 机械工业出版社，2013年4月第1版。
\bibitem{sauer} Timothy Sauer(著).裴玉茹.马赓宇(译). {数值分析}. 机械工业出版社. 2018年8月第1版. 
\bibitem{strang} Gilbert Strang. {Linear Algebra and Learning from Data}. Wellesley-Cambridge Press, 2019. 

\bibitem{tim-baumann} Tim Baumann. Image Compression with Singular Value Decomposition. \\ 
\url{http://timbaumann.info/svd-image-compression-demo/}

\end{thebibliography}


\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\end{document}

